package com.lw.leetcode.node;

/**
 * 687. 最长同值路径
 *
 * @Author liw
 * @Date 2021/5/12 10:11
 * @Version 1.0
 */
public class LongestUnivaluePath {

    public static void main(String[] args) {
        LongestUnivaluePath test = new LongestUnivaluePath();
        TreeNode node = TreeNode.getInstance4();
        int i = test.longestUnivaluePath(node);
        System.out.println(i);

    }

    int max = 1;
    public int longestUnivaluePath(TreeNode root) {

        find(root);
        return max - 1;
    }

    private int find (TreeNode root) {
        if (root == null) {
            return 0;
        }
        int l = 0;
        int r = 0;
        if (root.left != null) {
            int i = find(root.left);
            if (root.val == root.left.val) {
                l = i;
            }
        }
        if (root.right != null) {
            int i = find(root.right);
            if (root.val == root.right.val) {
                r = i;
            }
        }
        max = Math.max(l + r + 1, max);
        return Math.max(l, r) + 1;
    }

}
